1. Field of the Invention
The present invention relates to cyclic redundancy checks (CRCs). More specifically, the techniques of the present invention provide mechanisms for efficiently performing cyclic redundancy checks on programmable chips.
2. Description of Related Art
Cyclic redundancy checks (CRCs) are used in many communication and storage applications to detect data corruption. In a typical example, a message (M) is divided by a polynomial (P) known to both a sender and a receiver. The remainder (R) is transmitted with the message (M) to the receiver. The receiver uses the remainder (R) to verify that the message (M) has not been corrupted. R is referred to also as the Frame Check Sequence (FCS) or as a CRC. Although it is possible that different messages can give the same remainder R when divided by a polynomial (P), CRC computations have been highly effective, as the probability that corrupted data can pass a 32 bit CRC (CRC32) check is remote.
Galois field division is often used to determine R. Galois field division is implemented using shift registers and exclusive OR (XOR) gates on a programmable chip. In a simplified example, division can be performed by performing one XOR, bit shifting, performing another XOR, bit shifting, etc. However, to perform a CRC of 8 data bits, 8 clocks cycles would be required. To increase efficiency, it is well recognized that the bits in R or in a CRC can be calculated by performing XOR computations of various data and polynomial bits simultaneously.
However, performing these computations can be inefficient on programmable chips. That is, performing these computations may require many levels of logic or require a large amount of logic. Consequently, the techniques of the present invention provide efficient mechanisms for calculating CRCs on programmable chips.